/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {

    if (digits.length === 0) return [];
    const n = digits.length;
    const map = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz'
    };

    const queue = [];
    queue.push('');
    for (let i = 0; i < n; i++) {
        let size = queue.length;
        while (size--) {
            const curStr = queue.shift(); // 出列

            const letters = map[digits[i]];

            for (const letter of letters) {
                queue.push(curStr + letter); // 生成新的字母串入列
            }
        }
    }

    return queue; // 队列中全是最后一层生成的字母串
};